<?php
/**
 * User: helloJiu
 * Date: 2021/11/5
 * Time: 10:04
 */

namespace App\Algorithm\DP;


class CombinationSum4
{
    /**
     * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
     * 题目数据保证答案符合 32 位整数范围。
     * 示例 1：
     * 输入：nums = [1,2,3], target = 4
     * 输出：7
     * 解释：
     * 所有可能的组合为：
     * (1, 1, 1, 1)
     * (1, 1, 2)
     * (1, 2, 1)
     * (1, 3)
     * (2, 1, 1)
     * (2, 2)
     * (3, 1)
     * 请注意，顺序不同的序列被视作不同的组合。
     *
     * https://leetcode-cn.com/problems/combination-sum-iv
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function combinationSum4($nums, $target)
    {
        // $dp[$j]: 凑够$j的组合个数
        $dp = [];
        for ($j = 0; $j <= $target; $j++) {
            $dp[$j] = 0;
        }

        $dp[0] = 1;

        for ($j = 1; $j <= $target; $j++) {
            foreach ($nums as $num) {
                if ($j >= $num) {
                    $dp[$j] = $dp[$j] + $dp[$j - $num];
                }
            }
            print_r($dp);
        }
        /*
         *
        {1,1} {2} $dp[
        {1, 1, 1}   {2, 1}  {1, 2}
        $dp[3-1] + $dp[3]
        凑够$i 有dp[$i]中方法
        $dp[3] + $dp[2]..1
        $dp[3] + $dp[1]..2
        $dp[3] + $dp[0]..3
         *      0   1   2   3 (物品)
         0      1   1   1   1
         1      0   1   1   1
         2      0   1   2   2
         3      0   2   3   4
         4      0   1   6   7
        (背包)

         *      0   1   2   3   4 (背包)
         0      1   0   0   0   0
         1      1   1   1   1   1
         2      1   1   2   2   3
         3      1   1   2   3   4
        (物品)


         *
         */

        // [1,2,3], 4

        return $dp[$target];
    }
}